package Epic;

import java.util.ArrayList;



public class additiveNumber {
	
	public additiveNumber(){
		
	}
	
	public boolean isNumber(int n){
		ArrayList<Integer> digits = new ArrayList<>();
		while(n>0){
			digits.add(n % 10);
			n = n/10;
		}
		int num1=0;
		for(int i=digits.size()-1;i>digits.size()/2;--i){
			num1 = num1*10+digits.get(i);
			
			int num2=0;
			for(int j=i-1;j>(i-1)/2;--j){
				num2 = num2*10 + digits.get(j);	
//				if(num1==num2){			//this line is for start with 1
					if(helper(num1, num2, digits, j-1)){
						return true;
					}	
//				}
//				else{
//					continue;
//				}
			}
		}
		return false;
	}
	
	private boolean helper(int num1, int num2, ArrayList<Integer> digits, int pos){
		if(pos<0) return true;
		int num3=0;
		for(int i=pos;i>=0;i--){
			num3 = num3*10 + digits.get(i);
			int exp_num = num1+num2;
			if(num3==exp_num){
				if(helper(num2, num3, digits, i-1))
					return true;
			}
		}
		return false;
	}
	
	public boolean isNumber2(int input){
		String num = String.valueOf(input);
		int num1;
		int num2 = Integer.parseInt(num.substring(0,1));
		int num3 = Integer.parseInt(num.substring(1,2));
		for(int i=1;i<num.length()/2;i++){
			num1 = Integer.parseInt(num.substring(0,i));
			for(int j=i+1;j<num.length();j++){
				num2 = Integer.parseInt(num.substring(i,j));
				int index3 = j;
				int remain = Integer.parseInt(num.substring(j));
				while(num1+num2<=remain){
					num3 = num1+num2;
					String newNum = (new Integer(num3)).toString();
					int len = newNum.length();
					if(index3+len>num.length())
						break;
					
					if(num.substring(index3,index3+len).equals(newNum)){
						index3 += len;
						if(index3 == num.length()){
							return true;
						}
						num1 = num2;
						num2 = num3;
						remain = Integer.parseInt(num.substring(index3));
					}
					else{
						break;
					}
				}
			}		
		}
		return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		additiveNumber test = new additiveNumber();
		int number = 8917;
		System.out.println(test.isNumber(number));
		System.out.println(test.isNumber2(number));
	}

}
